package com.ztom.daily.n2022.m5;

import java.util.HashMap;
import java.util.Map;

/**
 * 贴纸拼词
 * <p>
 * https://leetcode.cn/problems/stickers-to-spell-word/
 *
 * @author ZhangTao
 */
public class Day14MinStickers {

    public int minStickers(String[] stickers, String target) {
        Map<String, Integer> cache = new HashMap<>();
        // 记录每张贴纸, 每个字符出现频次
        int[][] count = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            char[] chars = stickers[i].toCharArray();
            for (char c : chars) {
                count[i][c - 'a']++;
            }
        }
        cache.put("", 0);
        int res = process3(count, target, cache);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int process3(int[][] count, String target, Map<String, Integer> cache) {
        if (cache.containsKey(target)) {
            return cache.get(target);
        }
        char[] chars = target.toCharArray();
        int[] tcount = new int[26];
        for (char c : chars) {
            tcount[c - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for (int[] nums : count) {
            if (nums[chars[0] - 'a'] > 0) {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < 26; i++) {
                    if (tcount[i] > 0) {
                        for (int j = 0; j < tcount[i] - nums[i]; j++) {
                            builder.append((char) (i + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min, process3(count, rest, cache));
            }
        }
        min = min + (min == Integer.MAX_VALUE ? 0 : 1);
        cache.put(target, min);
        return min;
    }
}
